Lehmer-type conjectures and open problems for Nathanson’s totient functions

Abstract: Nathanson’s totient functions $\Phi(n)$ and $\Phi_k(n)$, where $\Phi(n)$ counts the number of nonempty sets $A \subseteq \{1, 2, \dots, n\}$ for which $\gcd(A)$ is relatively prime to $n$, and $\Phi_k(n)$ restricts those of size $k$. We formulate and analyze some analogue of Lehmer's conjecture in the setting of Nathanson’s totient functions $\Phi(n)$ and $\Phi_k(n)$. We further discuss divisibility phenomena for $\Phi(n)$. We conclude with several conjectures and open problems concerning density, arithmetic progressions, and further structural properties of these functions.

number theory

Audience: researchers in the topic

Combinatorial and additive number theory seminar (CANT 2026)